#include "../include/rbtree.h"
#include "../include/queue.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

long N;

typedef struct node_s {
	unsigned long black_count;
        unsigned long n;
	queue_t  queue;	
        rbtree_t rbtree;
}node_t;

#define BITMAP_ERROR 0;
#define BITMAP_OK    1;

#define BIT_CLR      0
#define BIT_SET      1



typedef struct bitmap_s{
        /*有几个bit位*/
        unsigned long bits;
        /*为0个数*/
        unsigned long zero_count;
        /*为1的个数*/
        unsigned long one_count;
        /*字节数组*/
        char buf[];
}bitmap_t, *bmap ;




void bitmap_init(bmap *bitmap, unsigned long size);
unsigned long bitmap_set_count(bmap bitmap);
unsigned long bitmap_clr_count(bmap bitmap);
void bitmap_clear(bmap bitmap);
void bitmap_full(bmap bitmap);
int  bitmap_set(bmap bitmap, unsigned long, int flag);
void bitmap_free(bmap bitmap);
int  bitmap_get(bmap bitmap, unsigned long index);

void bitmap_init(bmap * bitmap, unsigned long size){
         unsigned long nbytes;
         nbytes = size / 8 + ((size % 8) == 0 ? 0 : 1);

         *bitmap = malloc(sizeof(bitmap_t) + nbytes*sizeof(char));
         memset((*bitmap)->buf, 0x00, nbytes);
         (*bitmap)->bits = size;
         (*bitmap)->zero_count = size;
         (*bitmap)->one_count  = (*bitmap)->bits - (*bitmap)->zero_count;
}

unsigned long bitmap_set_count(bmap bitmap) {
        return bitmap->one_count;
}
unsigned long bitmap_clr_count(bmap bitmap) {
        return bitmap->zero_count;
}
unsigned long bitmap_length(bmap bitmap) {
        return bitmap->bits;
}
unsigned long bitmap_clr_count(bmap bitmap);

void bitmap_clear(bmap bitmap) {
        unsigned long nbytes;
        nbytes = bitmap->bits / 8 + ((bitmap->bits % 8) == 0 ? 0 : 1);

        memset(bitmap->buf, 0x00, nbytes);
        bitmap->zero_count = bitmap->bits;
        bitmap->one_count = 0;
}

void bitmap_full(bmap bitmap) {
        unsigned long nbytes;
        nbytes = bitmap->bits / 8 + ((bitmap->bits % 8 == 0) ? 0 : 1);

        memset(bitmap->buf, 0xff, nbytes);
        bitmap->zero_count = 0;
        bitmap->one_count = bitmap->bits;
}

int  bitmap_set(bmap bitmap, unsigned long index, int flag){
        unsigned long seg;
        unsigned offset;
        unsigned char * p;
        unsigned char tmp;
        if(index >= bitmap->bits)
                return BITMAP_ERROR;
        seg         = index / 8;
        offset      = index % 8;
        p = bitmap->buf + seg;

        if(flag == BIT_SET && BIT_SET != bitmap_get(bitmap, index)){
                tmp  = 0x1<<(8-offset-1);
                *p |= tmp;
                --bitmap->zero_count;
                ++bitmap->one_count;
        }
        else if(flag == BIT_CLR && BIT_CLR != bitmap_get(bitmap, index)){
                tmp = (0x1<<(8-offset-1))-1;
                *p &= tmp;
                ++bitmap->zero_count;
                --bitmap->one_count;
        }
        return BITMAP_OK;
}


int bitmap_get(bmap bitmap, unsigned long index){
        unsigned long seg;
        unsigned offset;
        int tmp;
        if(index >= bitmap->bits)
                return BITMAP_ERROR;
        seg         = index / 8;
        offset      = index % 8;
        tmp         = bitmap->buf[seg] & (0x1<<(8-offset-1));
        return tmp > 0 ? BIT_SET : BIT_CLR;
}

void bitmap_free(bmap bitmap){
        if(bitmap != NULL){
                free(bitmap);
        }
}

bool check_rbtree(rbtree_head_t * head) {
	node_t * pnode, * pfnode;
	queue_t qhead;
	queue_t * pqueue;
	rbtree_t *p = head->root;	
	rbtree_t *pf;
	int flag = 0;
	int black_count;
	init_head(queue_t, &qhead);

	if (rbtree_is_empty(head)) {
		return true;
	}	
	pnode = entry(p, node_t, rbtree);
/*校验性质4)5）*/
	queue_push(&qhead, &(pnode->queue));	
	while ((pqueue = queue_pop(&qhead)) != NULL) {	
		pnode = entry(pqueue, node_t, queue);
		p = &(pnode->rbtree);
		if (rbtree_is_root(p)) {
			pnode->black_count = 1;
		}
		else {
			pfnode = entry(p->father, node_t, rbtree);
			if (p->color == BLACK) {
				pnode->black_count = pfnode->black_count + 1;
			}
			else {
				pnode->black_count = pfnode->black_count;
				/* 检验性质 4) */
				if (p->father->color == RED) {
					printf("wrong1:rbtree\n");
					return false;
				}
			}
		}
		if (p->left == NIL && p->right == NIL) {
			if (0 == flag) {
				black_count = pnode->black_count;
				flag = 1;
			}
			else {
				/*检验性质 5)*/
				if (pnode->black_count != black_count) {
					printf("wrong2: rbtree\n");
					return false;
				}	
			}
			continue;
		}
		if (p->left != NIL) {
			pnode = entry(p->left, node_t, rbtree);
			queue_push(&qhead, &(pnode->queue));
		}
		if (p->right != NIL) {
			pnode = entry(p->right, node_t, rbtree);
			queue_push(&qhead, &(pnode->queue));
		}
	}
/*检验性质2）*/
	if (head->root->color == RED) {
		printf("wrong3:rbtree\n");	
		return false;
	}
	return true;
}
void check_rbtree_unrandom() {
        rbtree_head_t head;
	rbtree_t * punit;
	int i = 0;
        struct timeval ts,te;
        node_t * p;

        srand(time(0));

        p = calloc(N, sizeof(node_t));
        init_head(rbtree_head_t, &head);

        for (i = 0; i < N; ++i) {
                rbtree_set_key(&(p[i].rbtree), i);
		if (1==i || 10==i || 100==i || 1000==i || 10000==i || 100000==i || 1000000==i || 10000000==i)		
			gettimeofday(&ts, NULL);
                rbtree_insert(&head, &(p[i].rbtree));
		if (1==i || 10==i || 100==i || 1000==i || 10000==i || 100000==i || 1000000==i || 10000000==i)	{	
			gettimeofday(&te, NULL);
			printf("n=%d insert waster time:%d us\n", i, 1000000 * (te.tv_sec - ts.tv_sec) + (te.tv_usec - ts.tv_usec));
		}
        }
	printf("\n");

        for (i = N-1; i >= 0; --i) {
		punit = rbtree_find(&head, i);
		if (1==i || 10==i || 100==i || 1000==i || 10000==i || 100000==i || 1000000==i || 10000000==i)		
			gettimeofday(&ts, NULL);
                 rbtree_delete(punit);
		if (1==i || 10==i || 100==i || 1000==i || 10000==i || 100000==i || 1000000==i || 10000000==i)	{	
			gettimeofday(&te, NULL);
			printf("n=%d delete waster time:%d us\n", i, 1000000 * (te.tv_sec - ts.tv_sec) + (te.tv_usec - ts.tv_usec));
		}
	}
}

void check_rbtree_random() {
	long n;
	rbtree_head_t head;
	rbtree_t * punit;

        struct timeval ts,te;
        node_t * p;
	unsigned long count = 0;
        bmap bitmap;	

	srand(time(0));

	p = calloc(N, sizeof(node_t));	
	init_head(rbtree_head_t, &head);
	bitmap_init(&bitmap, N);
	
	gettimeofday(&ts, NULL);
	while (1) {
		n = rand() % N;
                if (bitmap_get(bitmap, n) == BIT_CLR) {
                        count++;
                        bitmap_set(bitmap, n, BIT_SET);
			rbtree_set_key(&(p[n].rbtree), n);
			rbtree_insert(&head, &(p[n].rbtree));
			if (n % N == 1000) {
				if (false == check_rbtree(&head)) {
					printf("wrong: rbtree_insert\n");
					return ;
				}
			}
                }
                else if (count == N) {
                        break;
                }	
	}	
	gettimeofday(&te, NULL);
	bitmap_free(bitmap);

	printf("insert waster time:%d us\n", 1000000 * (te.tv_sec - ts.tv_sec) + (te.tv_usec - ts.tv_usec));

	gettimeofday(&ts, NULL);

	bitmap_init(&bitmap, N);
	count = 0;
	while (1) {
		n = rand() % N;
		if (bitmap_get(bitmap, n) == BIT_CLR) {
			count++;
			bitmap_set(bitmap, n, BIT_SET);
			punit = rbtree_find(&head, n);
                	rbtree_delete(punit);

			if (n % N == 1000) {
				if (false == check_rbtree(&head)) {
					printf("wrong: rbtree_delete\n");
					return ;
				}
			}

		}
		else if (count == N) {
			break;
		}	
	}
	bitmap_free(bitmap);
	gettimeofday(&te, NULL);
	printf("delete  waster time:%d us\n", 1000000 * (te.tv_sec - ts.tv_sec) + (te.tv_usec - ts.tv_usec));
	printf("right: rbtree_insert_delete\n");
}

void check_rbtree_insert_delete() {
	long i ;
	long count;
	rbtree_head_t head;
	rbtree_t * punit;

        struct timeval ts,te;
        node_t * p;

	srand(time(0));

	p = calloc(N, sizeof(node_t));	
	init_head(rbtree_head_t, &head);
	
	gettimeofday(&ts, NULL);
        for (i = 0; i < N; ++i) {
                rbtree_set_key(&(p[i].rbtree), i);
                rbtree_insert(&head, &(p[i].rbtree));
        }
	gettimeofday(&te, NULL);
	printf("insert waster time:%d us\n", 1000000 * (te.tv_sec - ts.tv_sec) + (te.tv_usec - ts.tv_usec));
	printf("\n");

	gettimeofday(&ts, NULL);
        for (i = N-1; i >= 0; --i) {
		punit = rbtree_find(&head, i);
                rbtree_delete(punit);
	}
	gettimeofday(&te, NULL);
	printf("delete waster time:%d us\n", 1000000 * (te.tv_sec - ts.tv_sec) + (te.tv_usec - ts.tv_usec));
}

int main(int argc, char *argv[]) {
	if (argc != 2) {
		printf("rbtree_test n\n");
		return 1;
	}
	N = atol(argv[1]);
	if (N == 0) {
		printf("n must lager then 0\n");
		return 1;
	}
//	check_rbtree_random();
//	check_rbtree_insert_delete();
	check_rbtree_unrandom();
	return 0;
}

